package com.peng.leetcode.tree;

/**
 * MaxPathSum
 *
 * 124. 二叉树中的最大路径和
 *
 * @author: lupeng6
 * @create: 2021/1/28 18:31
 */
public class MaxPathSum {

    public static void main(String[] args) {

    }

    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return maxSum;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.left != null && node.right != null) {
            int sum = node.val + node.left.val + node.right.val;
            maxSum = Math.max(sum, maxSum);
        }
        dfs(node.left);
        dfs(node.right);
    }
}
